#include <stdio.h>

#define MAX 10
#define N 9 // 最大长度

// 静态链表的节点结构体
typedef struct
{
    int data; // 存储数据
    int next; // 存储下一个节点的索引
} Node;

// 全局静态链表数组
Node list[N];

// 创建静态链表
void createStaticList(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        list[i].data = arr[i];
        list[i].next = (i == n - 1) ? -1 : i + 1; // 最后一个元素的next为-1，表示链表结束
    }
}

// 打印静态链表
void printList(int startIndex)
{
    int index = startIndex;
    while (index != -1)
    {
        printf("%d ", list[index].data);
        index = list[index].next;
    }
    printf("\n");
}

// 计数排序（按某一位排序）
void countingSort(int n, int exp)
{
    int count[MAX] = {0}; // 计数数组，数字范围是0-9
    int output[n];        // 输出数组
    int index;

    // 统计每个数字在当前位的出现次数
    for (int i = 0; i < n; i++)
    {
        index = list[i].data / exp % 10;
        count[index]++;
    }

    // 修改计数数组，使其包含每个数字的实际位置
    for (int i = 1; i < MAX; i++)
    {
        count[i] += count[i - 1];
    }

    // 构建输出数组
    for (int i = n - 1; i >= 0; i--)
    {
        index = list[i].data / exp % 10;
        output[count[index] - 1] = list[i].data;
        count[index]--;
    }

    // 将排序后的数据写回静态链表
    for (int i = 0; i < n; i++)
    {
        list[i].data = output[i];
    }
}

// 基数排序（通过静态链表）
void radixSort(int n)
{
    // 找到最大值，确定排序的位数
    int max = list[0].data;
    for (int i = 1; i < n; i++)
    {
        if (list[i].data > max)
        {
            max = list[i].data;
        }
    }

    // 从个位开始按每一位排序，直到最大值的最高位
    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        countingSort(n, exp);
    }
}

int main()
{
    int arr[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 创建静态链表
    createStaticList(arr, n);

    printf("原始静态链表: ");
    printList(0); // 从链表的起始位置打印

    // 执行基数排序
    radixSort(n);

    printf("排序后的静态链表: ");
    printList(0); 

    return 0;
}
